package algorithm.binary_tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 多叉树基础操作
 */
public class MultiTree {
    static class MultiTreeNode{
        int value;
        List<MultiTreeNode> children;

        MultiTreeNode(int value){
            this.value = value;
            children = new ArrayList<>();
        }
    }

    MultiTreeNode root;

    // 添加节点
    public void addNode(int parentValue, int value){
        if (root == null){
            root = new MultiTreeNode(value);
            return;
        }
        addNodeRecursive(root, parentValue, value);
    }

    private void addNodeRecursive(MultiTreeNode node, int parentValue, int value){
        // 终止条件
        if (node.value == parentValue){
            node.children.add(new MultiTreeNode(value));
            return;
        }
        for(MultiTreeNode child : node.children){
            addNodeRecursive(child, parentValue, value);
        }
    }
    
    // 删除节点
    public void deleteNode(int value){
        if (root == null){
            return;
        }
        if (root.value == value){
            root = null;
            return;
        }
        deleteNodeRecursive(root, value);
    }
    
    private boolean deleteNodeRecursive(MultiTreeNode parent, int value){
        List<MultiTreeNode> children = parent.children;
        for(int i = 0; i < children.size(); i++){
            MultiTreeNode child = children.get(i);
            if (child.value == value){
                children.remove(i);
                return true;
            }else{
                if (deleteNodeRecursive(child, value)){
                    return true;
                }
            }
        }
        return false;
    }

    // 查询节点是否存在
    public boolean containsNode(int value){
        return containsNodeRecursive(root, value);
    }

    private boolean containsNodeRecursive(MultiTreeNode node, int value){
        if (node == null){
            return false;
        }
        if (node.value == value){
            return true;
        }
        for(MultiTreeNode child : node.children){
            if (containsNodeRecursive(child, value)){
                return true;
            }
        }
        return false;
    }

    // 深度优先遍历-前序遍历
    void depthFirstPerOrder(MultiTreeNode root){
        if (root == null){
            return;
        }
        System.out.println(root.value + " ");
        for(MultiTreeNode child : root.children){
            depthFirstPerOrder(child);
        }
    }

    void depthFirstInOrder(MultiTreeNode root){
        if (root == null){
            return;
        }
        if (!root.children.isEmpty()){
            depthFirstInOrder(root.children.get(0));
        }
        System.out.println(root.value + " ");
        for (int i = 1; i < root.children.size(); i++) {
            depthFirstInOrder(root.children.get(i));
        }
    }

    void depthFirstPostOrder(MultiTreeNode root){
        if (root == null){
            return;
        }
        for(MultiTreeNode child : root.children){
            depthFirstPostOrder(child);
        }
        System.out.println(root.value + " ");
    }

    // 广度优先遍历
    void breadthFirstTraversal(MultiTreeNode root){
        if (root == null){
            return;
        }
        Queue<MultiTreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            MultiTreeNode node = queue.poll();
            System.out.println(node.value + " ");
            queue.addAll(node.children);
        }
    }
}
